﻿// 0814train02.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>
#include <limits>
#include <unordered_map>
#include <unordered_set>

using namespace std;

/*
 有 n 个城市，其中一些彼此相连，另一些没有相连。
 如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。
省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。
给你一个 n x n 的矩阵 isConnected ，
其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，
而 isConnected[i][j] = 0 表示二者不直接相连。
返回矩阵中 省份 的数量。
 */

void DFS01(vector<vector<int>>&grid, vector<bool>&checked_vec, int index)
{
    //标记为已访问
    checked_vec[index] = true;

    //i!=j !vistited 不为0
    vector<int>curr_vec = grid[index];

    for (int i=0; i<curr_vec.size(); i++)
    {
        bool is_available = curr_vec[i] == 1;
        bool is_visited = checked_vec[i];
	    if (i!=index && !is_visited && is_available)
	    {
            DFS01(grid, checked_vec, i);
	    }
    }

    //DFS01------
}

int findCircleNum(vector<vector<int>>& isConnected) {
    //isConnected = [[1,1,0],[1,1,0],[0,0,1]]
    int grid_size = isConnected.size();
    vector<bool>checked_vec(grid_size, false);

    int result = 0;
    for (int i=0; i<grid_size; i++)
    {
        bool is_visited = checked_vec[i];
        //未访问
        if (!is_visited)
        {
            DFS01(isConnected, checked_vec, i);
            result += 1;
        }
    }
    return result;
    //findCircleNum------
}


/*
 给你一个 n x n 的关联矩阵 isConnected ，其中 isConnected[i][j] = 1
 表示第 i 个发行版和第 j 个发行版直接关联，
 而 isConnected[i][j] = 0 表示二者不直接相连。
返回最大的发行版集中发行版的数量。

输入描述
第一行输入发行版的总数量 N，之后每行表示各发行版间是否直接相关。
输出描述
输出最大的发行版集中发行版的数量

输入
4
1 1 0 0
1 1 1 0
0 1 1 0
0 0 0 1
输出
3
 */

class DFSClass02
{
public:
    void DFS(vector<vector<int>>&grid, vector<bool>&checked_vec, int curr_index)
    {
        //标记已访问
        checked_vec[curr_index] = true;
        curr_count += 1;

        vector<int>curr_vec = grid[curr_index];

        //i!=curr_index curr_vec[i]==1 未访问
        for (int i=0; i<curr_vec.size(); i++)
        {
            bool is_visited = checked_vec[i];
            bool is_available = curr_vec[i] == 1;
            if (i!=curr_index && !is_visited && is_available)
            {
                DFS(grid, checked_vec, i);
            }
            //for------
        }

        //DFS------
    }

    void solve02(vector<vector<int>>& grid)
    {
        int grid_size = grid.size();

        //checked_vec DFS
        vector<bool>checked_vec(grid_size, false);

        int result = 0;
        for (int i=0; i<grid_size; i++)
        {
            //未访问
            bool is_visited = checked_vec[i];

            if (!is_visited)
            {
                DFS(grid, checked_vec, i);

                result = max(result, curr_count);
                curr_count = 0;
            }

            //for---
        }

        cout << result;
        //isConnected------
    }

private:
    int curr_count = 0;
    //DFSClass02
};

/*
 4
1 1 0 0
1 1 1 0
0 1 1 0
0 0 0 1
 */

/*
 有 n 个房间，房间按从 0 到 n - 1 编号。
 最初，除 0 号房间外的其余所有房间都被锁住。
 你的目标是进入所有的房间。然而，你不能在没有获得钥匙的时候进入锁住的房间。
当你进入一个房间，你可能会在里面找到一套不同的钥匙，每把钥匙上都有对应的房间号，即表示钥匙可以打开的房间。
你可以拿上所有钥匙去解锁其他房间。
给你一个数组 rooms 其中 rooms[i] 是你进入 i 号房间可以获得的钥匙集合。
如果能进入 所有 房间返回 true，否则返回 false。
 */

class Solution {
public:
    void DFS(vector<vector<int>>&grid, vector<bool>&checked_vec, 
        unordered_set<int>&key_set,
        int curr_index)
    {
        //标记为已访问
        checked_vec[curr_index] = true;
        vector<int>curr_vec = grid[curr_index];

        //next_index!=curr_index 未访问
        for (int i=0; i<curr_vec.size(); i++)
        {
            int next_index = curr_vec[i];
            key_set.insert(next_index);

            bool is_visited = checked_vec[next_index];

            if (next_index!=curr_index && !is_visited)
            {
                DFS(grid, checked_vec, key_set, next_index);
            }
            //for------
        }

        //DFS---
    }

    bool canVisitAllRooms(vector<vector<int>>& rooms) {

        //1size 2checked_vec 3循环
        int grid_size = rooms.size();

        vector<bool>checked_vec(grid_size, false);

        unordered_set<int>key_set;

        for (int i=0; i<grid_size; i++)
        {
            //是否拿到钥匙
            bool is_available = i == 0 || key_set.count(i) > 0;
            if (!checked_vec[i]&& is_available)
            {
                DFS(rooms, checked_vec, key_set, i);

            }

            //for---
        }

        //for (auto item:checked_vec)
        //{
        //    cout << item << ' ';
        //}
        //cout << '\n';
        bool result = true;
        for (auto status:checked_vec)
        {
            if (!status) result = false;
        }

        return result;
        //canVisitAllRooms
    }
};

int main()
{
	{
        //rooms = [[1],[2],[3],[]]
        //rooms = [[1,3],[3,0,1],[2],[0]]
        vector<vector<int>>rooms = { {1,3},{3,0,1},{2},{0}};
        Solution solu;
        cout << solu.canVisitAllRooms(rooms);


        return 0;
	}
	{
        //vector<int>vec1 = { 1,1,0,0 };
        //vector<int>vec2 = { 1,1,1,0 };
        //vector<int>vec3 = { 0,1,1,0 };
        //vector<int>vec4 = { 0,0,0,1 };
        //vector<vector<int>>grid = { vec1, vec2, vec3, vec4 };
        int vec_size;
        cin >> vec_size;
        vector<vector<int>>grid(vec_size, vector<int>(vec_size));

        for (int r=0; r<vec_size; r++)
        {
            for (int c=0; c<vec_size; c++)
            {
                cin >> grid[r][c];
            }
        }

        DFSClass02 dfs_class;
        dfs_class.solve02(grid);

        return 0;
	}


    //isConnected = [[1,1,0],[1,1,0],[0,0,1]]
    vector<vector<int>>isConnected = { {1,1,0},{1,1,0},{0,0,1} };
    cout << findCircleNum(isConnected);
    //main------
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
